1. Field of the Invention
This invention relates to symmetric multiprocessor synchronization and implicit synchronization of resources using migrating scheduling domains, as described herein.
2. Related Art
In computer systems having multiple processors with concurrent execution, it is desirable to use as much of the parallelism as possible from the multiple processors. One problem with using the parallelism of multiple processors is that of designing software to make use of that parallelism. For example, software that was designed for use with a uniprocessor system often does not exploit the parallelism of a multiprocessor system to the fullest extent possible.
A first known method is to redesign or rewrite software originally designed for use with a uniprocessor system, so as to make use of the advantages of a multiprocessor system. While this known method does generally achieve the goal of using the advantages of a multiprocessor system, it is subject to several drawbacks. First, it is extremely expensive, in that it uses relatively large amounts of (human design and coding) resources for redesigning or rewriting program code. Second, it is sometimes then necessary to maintain two different code bases, one for uniprocessor systems and one for multiprocessor systems, also resulting in additional expense and use of human design and coding resources.
A second known method is to introduce (into software originally designed for use with a uniprocessor system) those explicit synchronization methods for maintaining integrity of resources to be shared among multiple processors. While this known method generally achieves the same goal with relatively less expense and consumption of resources than a complete redesign or rewrite of the software code base, it also suffers from several drawbacks. First, it introduces a relatively large amount of new code subject to possible error in coding. Second, it introduces additional processor and memory usage to implement known explicit synchronization methods (such as locking mechanisms), with resulting slowing of the system using those known explicit synchronization methods. The second drawback is particularly exacerbated for resources that are primarily used by only one software element, but find occasional use by a second software element; the first software element pays the price of known explicit synchronization methods for each use of the resource, even though contention for that resource might be relatively rare. Moreover, these drawbacks for this second known method are also applicable to the first known method, as a new design would likely employ explicit synchronization methods.
A third known method is to identify (within software originally designed for use with a uniprocessor system) those functional elements that can each independently operate without using known explicit synchronization methods. An example of this third known method is shown in U.S. Pat. No. 5,485,579; in that patent, each separated functional element is bound to a single processor in a multiprocessor system, so that the system can assure that each processor is performing functions that do not require known explicit synchronization methods. While this method generally achieves the goal of using the advantages of a multiprocessor system, it is subject to several drawbacks. First, the mapping between separated functional elements and processors is 1:1, so if the number of separated functional elements differs from the number of processors, the system will either underutilize at least some of the processors or underperform the functions of at least some of the separated functional elements. Second, there is no provision for load balancing among the multiple processors. Third, there is no useful technique for altering the code base so as to make use of greater parallelism, without resorting to the first known method described above.
Accordingly, it would be advantageous to provide a technique for scheduling a set of tasks in a multiprocessor system that is not subject to drawbacks of the known art. In a preferred embodiment, this is achieved using a method and system for providing parallel execution of those tasks while implicitly synchronizing access to a set of resources (such as data structures or hardware devices) used by that system.